
public class IntArrayList {
  // 元素的数量
  private int size;

  // 所有元素
  private int[] elements;

  private static final int DEFAULT_CAPATICY = 2;
  private static final int ELEMENT_NOT_FOUND = -1;

  public IntArrayList(int capaticy) {
    capaticy = (capaticy < DEFAULT_CAPATICY) ? DEFAULT_CAPATICY : capaticy;
    elements = new int[capaticy];
  }

  public IntArrayList() {
    this(DEFAULT_CAPATICY);
  }

  // 清楚所有元素
  public void clear() {
    size = 0;
  }

  // 元素的数量
  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  // 是否包含某个元素
  public boolean contains(int element) {
    return indexOf(element) != ELEMENT_NOT_FOUND;
  }

  public void add(int element) {
    add(size, element);
  }

  public void add (int index, int element) {
    rangeCheckForAdd(index);

    ensureCapacity(size + 1);

    for (int i = size - 1; i >= index; i--) {
      elements[i + 1] = elements[i];
    }
    elements[index] = element;
    size ++;
  }

  // 获取index位置的元素 
  public int get(int index) {
    rangeCheck(index);
    return elements[index];
  }

  // 设置index位置的元素
  public int set(int index, int element) {
    rangeCheck(index);
    int old = elements[index];
    elements[index] = element;
    return old;
  }

  // 删除index位置元素
  public int remove(int index) {
    int old = get(index);
    if (index <= size -1) {
      for (int i = index + 1; i < size; i++) {
        elements[i - 1] = elements[i];
      }
    }
    size --;
    return old;
  }

  public int indexOf(int element) {
    for (int i = 0; i < size; i++) {
      if (elements[i] == element) return i;
    }
    return ELEMENT_NOT_FOUND;
  }

  // 保证要有 capacity 的容量
  private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;

    // OC 系数为 1.6
    // Java 系数 1.5
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新容量为旧容量 的 1.5倍。位移的小数处理 精度比较高(java浮点运算有精准度问题)

    // int newCapacity = oldCapacity << 1; // 2倍
    int[] newElement = new int[newCapacity];
    for (int i = 0; i < size; i++) {
      newElement[i] = elements[i];
    }
    elements = newElement;
    System.out.println("扩容：" + oldCapacity + "_ 扩容为" + newCapacity);
  }

  private void outOfBounds(int index) {
    throw new IndexOutOfBoundsException("index:" + index + ", size:" + size);
  }
  private void rangeCheck(int index) {
    if (index < 0 || index >= size ) {
      outOfBounds(index);
    }
  }

  private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size ) {
      outOfBounds(index);
    }
  }

  @Override
  public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(", [");

    for (int i = 0; i < size; i++) {
      if (i != 0) { // 1
        string.append(", ");
      }

      string.append(elements[i]);

      // if (i != size - 1) { // 2 : 有一个减法的操作，不如1好
      //   string.append(", ");
      // }
    }

    string.append("]");
    return string.toString();
  }
}